package com.lmk.dsa.struct.heap;

import com.lmk.dsa.struct.commons.KvNode;

/**
 * 最大索引堆
 * @author LaoMake
 * @since 1.0
 */
public class MaxIndexHeap extends IndexHeap {

    public MaxIndexHeap() {
    }

    public MaxIndexHeap(int capacity) {
        super(capacity);
    }

    @Override
    protected void siftUp(int index) {
        if(index <= 0){
            return;
        }

        int parentIndex = parent(index);
        KvNode child = (KvNode) data[indexes[index]];
        KvNode parent = (KvNode) data[indexes[parentIndex]];

        if(child.key.compareTo(parent.key) > 0){
            swapIndexes(index, parentIndex);
            // 同步反向查找索引
            reverse[indexes[index]] = index;
            reverse[indexes[parentIndex]] = parentIndex;
            siftUp(parentIndex);
        }
    }

    @Override
    protected void siftDown(int index) {
        if(index < 0 || index >= size){
            return;
        }

        int childIndex = leftChild(index);
        if(childIndex < size){
            KvNode parent = (KvNode) data[indexes[index]];

            KvNode child = (KvNode) data[indexes[childIndex]];
            if(childIndex + 1 < size){
                KvNode rightChild = (KvNode) data[indexes[childIndex + 1]];
                if(rightChild.key.compareTo(child.key) > 0){
                    child = rightChild;
                    childIndex++;
                }
            }

            if(child.key.compareTo(parent.key) > 0){
                swapIndexes(childIndex, index);
                reverse[indexes[index]] = index;
                reverse[indexes[childIndex]] = childIndex;

                siftDown(childIndex);
            }
        }
    }
}
